package algorithm_optimal_solution.StackAndQueue;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//单调栈：无重复值数组中找出左右边离i最近且比arr[i]小的值的下标。（如果是有重复数组，那么栈中的元素用List列表来替代）
// 要点：使用单调栈，查小递减，查大递增，遍历弹栈时左最近小值为弹出栈的下一位，右最近小值为当前位。清算弹栈时，左最近小值为弹出栈下一位，右最近小值没有
public class DrabStack {

    public void drabStackNoRepeat(int[] arr){
        Stack<Integer> stack = new Stack<>();
        int len = arr.length;
        int[][] twoArr = new int[len][2];
        for(int i=0;i<len;i++){
            while(!stack.isEmpty() && arr[stack.peek()] > arr[i]){
                int index = stack.pop();
                twoArr[index][0] = stack.isEmpty() ? -1 : stack.peek();
                twoArr[index][1] = i;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int value = stack.pop();
            twoArr[value][0] = stack.isEmpty() ? -1 : stack.peek();
            twoArr[value][1] = -1;
        }
        StringBuilder sb = new StringBuilder();
        for(int[] i:twoArr){
            sb.append(i[0]).append(" ").append(i[1]).append("\n");
        }
        System.out.print(sb);
    }

    public void drabStackRepeat(int[] arr){
        Stack<List<Integer>> stack = new Stack<>();
        int len = arr.length;
        int[][] twoArr = new int[len][2];
        for(int i=0;i<len;i++){
            while(!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]){
                List<Integer> indexList = stack.pop();
                int leftLess = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
                for(Integer index:indexList){
                    twoArr[index][0] = leftLess;
                    twoArr[index][1] = i;
                }
            }
            if(!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]){
                stack.peek().add(i);
            }else{
                List<Integer> newList = new ArrayList<>();
                newList.add(i);
                stack.push(newList);
            }
        }
        while(!stack.isEmpty()){
            List<Integer> indexList = stack.pop();
            int leftLess = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);
            for(Integer index:indexList){
                twoArr[index][0] = leftLess;
                twoArr[index][1] = -1;
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int[] i:twoArr){
            sb.append(i[0]).append(" ").append(i[1]).append("\n");
        }
        System.out.print(sb);
    }

    public static void main(String[] args)throws IOException{
        BufferedReader scanner = new BufferedReader(new InputStreamReader(System.in));
        int len = Integer.parseInt(scanner.readLine());
        String[] value = scanner.readLine().split(" ");
        int[] arr = new int[value.length];
        for(int i = 0;i<value.length;i++){
            arr[i] = Integer.parseInt(value[i]);
        }
        new DrabStack().drabStackNoRepeat(arr);
        new DrabStack().drabStackRepeat(arr);
    }
}
